/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: mac
 * Date: 2022-09-22
 * Time: 20:16
 */
//二叉树的每个节点的度 || 孩子个数 <= 2
//二叉树的每颗子树都是二叉树
//n0 = n2 + 1
//推导：
//假设二叉树有N个节点，一棵二叉树，要么n0，要么n1，要么n2
//N = n0 + n1 + n2;
//一个有N个节点的数，应该有N - 1条边
//度为0的节点 ，能产生多少条边？0
//度为1的节点有n1个，能产生多少条边？ n1
//度为2的节点有n2个，能产生多少条边？ 2 * n2
//N - 1 = 0 + n1 + 2 * n2 = n0 + n1 + n2 -1
//n0 = n2 + 1 !!!!!
//任何一颗二叉树，叶子节点一定比度为2的节点多一个
//任何一颗完全二叉树中，偶数个节点：n1 = 1 奇数个节点：n1 = 0;
//具有n个节点的完全二叉树的深度k为log2(n + 1)上取整
//ppt二叉树笔试题
//对于具有n个节点的完全二叉树，如果按照从上至下从左至右的顺序对所有节点从0开始编号
//则对于序号为i的节点有：
//○ 若i > 0 双亲结序号: (i - 1) / 2; i = 0 ，i为根
//○ 若2 * i + 1 < n,左孩子序号：2 * i + 1,否则无左孩子
//○ 若2 * i + 2 < n,右孩子： 2 * i + 2, 否则无右孩子

class BTNode1{
    int val;
    private BTNode1 left;//左孩子引用
    private BTNode1 right;//右孩子引用
    //做题以及面试常考
}
class BTNode2{
    int val;
    private BTNode2 left;//左孩子引用
    private BTNode2 right;//右孩子引用
    private BTNode2 parent;//双亲 - 该节点的根节点
    //AVL + 红黑 + B树会用
}
class BTNode3 {
    private char val;//数据域
    private BTNode3 firstChild;//第一个孩子节点
    private BTNode3 nextBrother;//从该节点往右第一个兄弟节点
}
public class TestDemo {
    public static void main(String[] args) {
        BinaryTree binaryTree = new BinaryTree();
        TreeNode root = binaryTree.createTree();
        binaryTree.preOrder(root);
        System.out.println();
        binaryTree.inOrder(root);
        System.out.println();
        binaryTree.postOrder(root);
    }
}
